Những khám phá khảo cổ học gần đây đã chứng minh rằng cư dân bản địa ở Phúc Kiến đã tiến vào thời đại đồ đá mới vào giữa thiên niên kỉ thứ 6 TCN. Từ di chỉ Xác Khâu Đầu (壳丘头, cách nay 7450–5590 năm), một di chỉ thời kỳ đầu đồ đá mới trên đảo Bình Đàm (平潭岛) nằm cách khoảng 70 kilômét (43 mi) về phía đông nam Phúc Châu, rất nhiều công cụ làm bằng đá, vỏ, mai, xương, ngọc thạch và gốm (gồm cả bàn xoay làm gốm) đã được khai quật, cùng với bánh xe quay, một bằng chứng của hoạt động dệt. Di chỉ Đàm Thạch Sơn (昙石山) (cách nay 5500–4000 năm) ở ngoại ô Phúc Kiến trải qua cả hai thời đại đồ đá mới và thời đại đồ đồng đá, tại đây đã tìm thấy các công trình tròn bán ngầm ở các mức thấp hơn. Di chỉ Hoàng Thổ Lôn (黄土崙) (khoảng 1325 TCN), cũng ở ngoại ô Phúc Châu, mang đặc điểm của thời đại đồ đồng.

Khu vực Phúc Kiến từng tồn tại vương quốc Mân Việt. Từ "Mân Việt" là kết hợp giữa từ "Mân" (閩/闽; Bạch thoại tự: bân), có thể là tên một dân tộc và có liên hệ với từ để chỉ các dân tộc man di trong tiếng Hán là "man" (蠻/蛮; bính âm: mán; Bạch thoại tự: bân), và "Việt" là lấy theo tên nước Việt thời Xuân Thu tồn tại ở khu vực tỉnh Chiết Giang ngày nay. Điều này là bởi vương tộc nước Việt đã bỏ chạy đến Phúc Kiến sau khi vương quốc của họ bị nước Sở tiêu diệt và sáp nhập vào năm 306 TCN. Mân cũng là tên của dòng sông chính trong khu vực Phúc Kiến, Mân Giang, song tên gọi người Mân có từ trước.

Nước Mân Việt tồn tại cho đến khi bị triều Tần bãi bỏ. Tuy nhiên, với việc Nhà Tần sớm sụp đổ, nội chiến đã nổ ra giữa Hạng Vũ và Lưu Bang, sử gọi là Hán Sở tranh hùng; khi đó Vô Chư (无诸) đã quyết định xuất quân phụ giúp Lưu Bang. Sau đó, Lưu Bang giành chiến thắng và lập ra triều Hán; để thưởng công, năm 202 TCN, Hán Cao Tổ phục hồi địa vị cho Mân Việt là một vương quốc chư hầu, phong Vô Chư là Mân Việt vương. Vô Chư được triều Hán cho phép xây thành phòng thủ ở Phúc Châu cũng như một số địa điểm khác tại Vũ Di Sơn, chúng đã được khai quật trong những năm gần đây. Vương quốc của Vô Chư đã mở rộng phạm vi ra ngoài ranh giới của Phúc Kiến đến các vùng đất mà nay là phía đông Quảng Đông, phía đông Giang Tây, và phía nam Chiết Giang.

Sau cái chết của Vô Chư, Mân Việt duy trì truyền thống chiến đấu của mình và tiến hành một số cuộc viễn chinh chống lại các nước chư hầu láng giềng tại Quảng Đông, Giang Tây, và Chiết Giang, việc này diễn ra trong suốt thế kỷ thứ II TCN và chỉ bị ngăn chặn bởi triều Hán. Cuối cùng, hoàng đế triều Hán đã quyết định loại bỏ mối đe dọa tiềm tàng này bằng cách gửi lực lượng quân sự lớn tấn công Mân Việt từ tứ phía cả trên biển lẫn trên bộ vào năm 111 TCN. Những người lãnh đạo ở Phúc Châu đã đầu hàng để tránh một cuộc chiến vô ích, tuy nhiên quân Hán vẫn tiến hành hủy hoại cung điện, thành quách của Mân Việt; vương quốc đầu tiên trong lịch sử Phúc Kiến kết thúc tồn tại một cách đột ngột.

Sau khi triều Hán dần sụp đổ vào cuối thế kỷ II, mở đường cho thời Tam Quốc. Tôn Quyền, người sáng lập ra nước Đông Ngô, đã phải mất gần 20 năm mới có thể khuất phục được người Sơn Việt, một nhánh Bách Việt sống ở vùng đồi núi. Làn sóng nhập cư đầu tiên của giới quý tộc người Hán đến khu vực Phúc Kiến ngày nay diễn ra vào đầu thế kỷ IV khi triều Tây Tấn sụp đổ và miền Bắc Trung Quốc bị các các dân tộc Hồ xâu xé. Những người nhập cư này chủ yếu đến từ tám dòng họ ở miền trung Trung Quốc: Lâm, Hoàng, Trần, Trịnh, Chiêm (詹), Khâu, Hà và Hồ. Bốn họ đầu tiên vẫn là những họ chính của người dân Phúc Kiến hiện nay.

Tuy nhiên, địa hình gồ ghề và biệt lập với các khu vực lân cận đã góp phần khiến cho nền kinh tế và mức độ phát triển của Phúc Kiến tương đối lạc hậu. Bất chấp việc số người Hán trong khu vực đã tăng đáng kể, mật độ dân số ở Phúc Kiến khi đó vẫn còn thấp so với phần còn lại của Trung Quốc. Triều Tấn chỉ lập ra 2 quận và 16 huyện trên đất Phúc Kiến ngày nay. Giống như các tỉnh phía nam khác như Quảng Đông, Quảng Tây, Quý Châu và Vân Nam, Phúc Kiến thường là một địa điểm để triều đình đương thời lưu đày các tù nhân và các nhân vật bất đồng. Đến thời Nam-Bắc triều, Phúc Kiến nằm dưới quyền kiểm soát của các hoàng triều phương Nam.

Thời Đường (618–907) là một thời kỳ hoàng kim của phong kiến Trung Quốc. Khi triều Đường sụp đổ, Trung Quốc bị chia cắt trong suốt một thời kỳ được gọi là Ngũ Đại Thập Quốc. Trong thời gian này, đã có một làn sóng nhập cư thứ hai đến Phúc Kiến để tìm chốn nương thân, dẫn đầu là Vương Thẩm Tri, người này đã lập ra nước Mân với kinh đô đặt tại Phúc Châu. Tuy nhiên, sau khi quốc vương khai quốc qua đời, Mân quốc đã xảy ra xung đột nội bộ và sớm bị một nước phương Nam khác là Nam Đường tiêu diệt.[6]

Tuyền Châu là một hải cảng phồn hoa dưới thời Mân. Vào đầu thời triều Minh, Tuyền Châu là khu vực binh lính tập hợp và cung cấp vật phẩm cho chuyến thám hiểm hàng hải của Trịnh Hòa. Việc hải cảng này phát triển hơn nữa bị cản trở do triều Minh đã ra lệnh hải cấm, và Tuyền Châu đã dần bị thay thế bởi các cảng Quảng Châu, Hàng Châu, Ninh Ba và Thượng Hải gần đó mặc dù lệnh cấm đã được gỡ bỏ vào năm 1550. Việc Uy khấu (hải tặc Nhật Bản) xâm nhập với quy mô lớn cuối cùng đã bị quân Trung Quốc và Toyotomi Hideyoshi của Nhật Bản xóa bỏ.

Thời Minh mạt và Thanh sơ đã xảy ra làn sóng lớn người tị nạn đến Phúc Kiến và 20 năm cấm buôn bán trên biển dưới thời Hoàng đế Khang Hy, một biện pháp nhằm chống lại những người vẫn trung thành với Nhà Minh tại Đài Loan dưới quyền lãnh đạo của Trịnh Thành Công. Tuy nhiên, những người tị nạn này đã không ở lại Phúc Kiến mà sau đó lại di cư đến các khu vực thịnh vượng ở Quảng Đông. Năm 1689, triều đình Nhà Thanh sau khi thu phục được Đài Loan đã chính thức hợp nhất hòn đảo này vào Phúc Kiến. Sau đó, người Hán bắt đầu di cư với số lượng lớn ra Đài Loan, và phần lớn cư dân Đài Loan hiện nay có nguồn gốc từ những người nhập cư đến từ miền Nam Phúc Kiến. Sau khi Đài Loan trở thành một tỉnh riêng vào năm 1885 và rồi bị nhượng cho Nhật Bản vào năm 1895, Phúc Kiến vẫn duy trì nguyên trạng cho đến nay. Phúc Kiến chịu ảnh hưởng đáng kể của Nhật Bản sau khi ký kết Hiệp ước Shimonoseki năm 1895 cho đến Chiến tranh Trung-Nhật trong Chiến tranh thế giới thứ hai.

Sau Cách mạng Tân Hợi, tỉnh Phúc Kiến nằm dưới quyền kiểm soát của chính quyền Trung Hoa Dân Quốc. Năm 1933, lộ quân 19 tiến hành binh biến và lập nên Trung Hoa Cộng hòa quốc, đặt thủ đô tại Phúc Châu. Nước cộng hòa này chỉ tồn tại trong 55 ngày từ 22 tháng 11 năm 1933 đến 13 tháng 1 năm 1934. Sau Nội chiến Trung Quốc, Phúc Kiến thuộc quyền kiểm soát của Cộng hòa Nhân dân Trung Hoa, riêng quần đảo Kim Môn và Mã Tổ do chính quyền Trung Hoa Dân Quốc tại Đài Loan chiếm giữ, chính quyền Trung Hoa Dân Quốc cũng thành lập nên tỉnh Phúc Kiến, song bộ máy chính quyền cấp tỉnh này hiện nay không hoạt động trên thực tế. Eo biển Đài Loan đã từng xảy ra ba cuộc khủng hoảng giữa hai bên vào các năm 1954-1955, 1958 và 1995–1996.

Kể từ cuối thập niên, kinh tế Phúc Kiến ở vùng ven biển đã hưởng lợi rất nhiều từ sự gần gũi về mặt địa lý và văn hóa với Đài Loan. Chính quyền Phúc Kiến và chính phủ Trung ương Trung Quốc cũng đề xuất thành lập khu kinh tế Bờ tây Eo biển để khai thác hiệu quả lợi thế này. Năm 2008, Đài Loan là nhà đầu tư số một tại Phúc Kiến.[7]